package dipl.algorithm.utility.data;

import dipl.algorithm.utility.data.comparator.IComparator;
import java.util.NoSuchElementException;

/**
 * Class implements a red-black-tree which is a binary search tree and
 * can be used for example as a priority-queue or dictionary.
 * All typical search-tree operations are supported in
 * time e O[log[n]] where n counts the number of elements in tree.
 *
 * @author Marko Walther
 * @param <T> class of keys in tree
 * @param <C> class of comparator for keys
 */
public class RedBlackTree<T, C extends IComparator<T>> {

	//
	// CLASSES
	//
	
	/**
	 * container for keys
	 */
	public class Item {
		/**
		 * item's key
		 */
		T key;
		/**
		 * node containing item
		 */
		Node node;
		/**
		 * construct item
		 */
		Item() {
			key = null;
			node = null;
		}
		/**
		 * @return key
		 */
		public T getKey() {
			return key;
		}
	}
	/**
	 * node in red-black-tree. a node must fulfill following two properties:
	 * 1. if a node is red, both children are black
	 * 2. every simple path from a node to a descendant leaf contains the same number
	 * 	  of black nodes.
	 */
	private class Node {
		/**
		 * left child
		 */
		Node left;
		/**
		 * right child
		 */
		Node right;
		/**
		 * parent node
		 */
		Node parent;
		/**
		 * color of node (black or red?)
		 */
		boolean red;
		/**
		 * item of node
		 */
		Item item;
		/**
		 * construct Node
		 */
		public Node() {
			left = null;
			right = null;
			parent = null;
			red = false;
			item = null;
		}
	}

	//
	// MEMBERS
	//
	
	/** */
	C comparator;
	/**
	 * number of key in tree
	 */
	int count;
	/**
	 * root of tree
	 */
	Node root;
	/**
	 * black nil-node of tree (sentinel for <code>null</code>)
	 */
	Node nil;

	//
	// CONSTRUCTOR METHODS
	//

	/**
	 * Constructs an empty rb-tree.
	 * @param comparator comparator to compare keys
	 */
	public RedBlackTree( C comparator ) {
		this.comparator = comparator;
		count = 0;
		nil = new Node();
		root = nil;
	}

	//
	// PUBLIC METHODS
	//

	/**
	 * Adds given key to tree and returns a tree-item associated with it.
	 * This item is needed as argument to the method removeItem.
	 * @param key key to add (must not be <code>null</code>
	 * otherwise an <code>IllegalArgumentException</code> is thrown.
	 * @return item containing key.
	 */
	public Item insertKey( T key ) {
		if( key == null )
			throw new IllegalArgumentException();
		Item item = new Item();
		item.key = key;
		Node x = new Node();
		x.left = nil;
		x.right = nil;
		x.item = item;
		item.node = x;
		treeInsert( x );
		count++;
		x.red = true;
		// rb-property violated: red parent must have black children
		// The invariant of this method is to leave the root black so that
		// x's grandparent exists (due to the rb-property )
		while( x != root && x.parent.red == true ) {
			Node gp = x.parent.parent;
			// parent is left child of grandparent
			if( x.parent == gp.left ) {
				// y is the uncle of x
				Node y = gp.right;
				if( y.red == true ) { // red uncle and red parent -> make them black
					x.parent.red = false;
					y.red = false;
					gp.red = true;
					x = gp;
				}
				else {
					if( x == x.parent.right ) {
						x = x.parent;
						leftRotate( x );
					}
					x.parent.red = false;
					gp.red = true;
					rightRotate( gp );
				}
			}
			else { // parent is right child of grandparent
				// y is the uncle of x
				Node y = gp.left;
				if( y.red == true ) { // red uncle and red parent -> make them black
					x.parent.red = false;
					y.red = false;
					gp.red = true;
					x = gp;
				}
				else {
					if( x == x.parent.left ) {
						x = x.parent;
						rightRotate( x );
					}
					x.parent.red = false;
					gp.red = true;
					leftRotate( gp );
				}
			}
		}
		root.red = false;
		return item;
	}
	/**
	 * @return maximum item in tree or <code>null</code> if tree is empty.
	 */
	public Item maximum() {
		if( root != nil )
			return treeMaximum( root ).item;
		return null;
	}
	/**
	 * @return minimum item in tree or <code>null</code> if tree is empty.
	 */
	public Item minimum() {
		if( root != nil )
			return treeMinimum( root ).item;
		return null;
	}
	/**
	 * method determines the predecessor of given item in this tree.
	 * @param e item whose successor is searched
	 * @return successor or <code>null</code> if no successor-found.
	 */
	public Item predecessor( Item e ) {
		Node s = treePredecessor( e.node );
		if( s != null )
			return s.item;
		return null;
	}
	/**
	 * Removes given item from tree.
	 * Throws a <code>NoSuchElementException</code> if tree is empty.
	 * Throws an <code>IllegalArgumentException</code> if item is <code>null</code>.
	 * @param item item to delete.
	 * @return key deleted.
	 */
	public T removeItem( Item item ) {
		if( count == 0 )
			throw new NoSuchElementException();
		if( item == null || item.key == null || item.node == null )
			throw new IllegalArgumentException();
		T key = item.key;
		Node z = item.node;
		Node y = null;
		if( z.left == nil || z.right == nil )
			y = z;
		else
			y = treeSuccessor( z );
		// splice out successor y which has at most one child.
		// x is child of successor
		Node x = null;
		if( y.left != nil )
			x = y.left;
		else
			x = y.right;
		x.parent = y.parent;
		if( y.parent == null )
			root = x;
		else {
			if( y == y.parent.left )
				y.parent.left = x;
			else
				y.parent.right = x;
		}
		if( y != z ) { // exchange data
			z.item = y.item;
			z.item.node = z;
		}
		if( y.red == false ) {
			deleteFixup( x );
		}
		count--;
		return key;
	}

	/**
	 * search given key in tree and returns the tree item if one exists.
	 * @param key key to search
	 * @return found item or <code>null</code>
	 */
	public Item search( T key ) {
		Node x = root;
		while( x != nil && comparator.compare( x.item.key, key ) != 0 ) {
			if( comparator.compare( key, x.item.key ) < 0 )
				x = x.left;
			else
				x = x.right;
		}
		if( x != nil )
			return x.item;
		return null;
	}

	/**
	 * method determines the successor of given item in this tree.
	 * @param e item whose successor is searched
	 * @return successor or <code>null</code> if no successor-found.
	 */
	public Item successor( Item e ) {
		Node s = treeSuccessor( e.node );
		if( s != null )
			return s.item;
		return null;
	}

	/**
	 * method can be used to test red-black-properties-
	 * @return <code>true</code> if all rb-properties are met, <code>false</code> otherwise
	 */
	public boolean testRBProperties() {
		if( root == nil )
			return true;
		// test property 1
		Stack< Node > stack = new Stack< Node >();
		stack.push( root );
		while( stack.count() != 0 ) {
			Node x = stack.pop();
			if( x.right != nil )
				stack.push( x.right );
			if( x.left != nil )
				stack.push( x.left );
			if( x.red == true ) {
				if( x.left != nil && x.left.red == true )
					return false;
				if( x.right != nil && x.right.red == true )
					return false;
			}
		}
		// test property 2
		stack.push( root );
		// in order to be balanced all paths from root to leafs must contain the same number of
		// black nodes
		while( stack.count() != 0 ) {
			Node x = stack.pop();
			int bh_r = blackHeight( x.right );
			int bh_l = blackHeight( x.left );
			if( bh_r != bh_l )
				return false;
			if( x.right != nil ) {
				stack.push( x.right );
			}
			if( x.left != nil ) {
				stack.push( x.left );
			}
		}
		return true;
	}

	//
	// PRIVATE METHODS
	//

	/**
	 * @param x
	 * @return black height of node.
	 * the black-height of a node is the number of black-nodes on any path from the node
	 * (but not including it) to a descendant leaf.
	 */
	private int blackHeight( Node x ) {
		int bh = -1;
		while( x != null ) {
			if( x.red == false )
				bh++;
			x = x.left;
		}
		return bh+1;
	}

	/**
	 * Fixes up the rb-properties after a node was removed from tree,
	 * beginning a node x
	 * @param x node
	 */
	private void deleteFixup( Node x ) {
		// x has a black extra which can be spend if x is red
		while( x != root && x.red == false ) {
			if( x == x.parent.left ) { // x is left child
				Node w = x.parent.right;
				if( w.red == true ) {
					w.red = false;
					w.parent.red = true;
					leftRotate( w.parent );
					w = x.parent.right;
				}
				if( w.left.red == false && w.right.red == false ) {
					w.red = true;
					x = x.parent;
				}
				else {
					if( w.right.red == false ) {
						w.left.red = false;
						w.red = true;
						rightRotate( w );
						w = x.parent.right;
					}
					w.red = x.parent.red;
					x.parent.red = false;
					w.right.red = false;
					leftRotate( x.parent );
					x = root;
				}
			}
			else { // x is right child
				Node w = x.parent.left;
				if( w.red == true ) {
					w.red = false;
					w.parent.red = true;
					rightRotate( w.parent );
					w = x.parent.left;
				}
				if( w.left.red == false && w.right.red == false ) {
					w.red = true;
					x = x.parent;
				}
				else {
					if( w.left.red == false ) {
						w.right.red = false;
						w.red = true;
						leftRotate( w );
						w = x.parent.left;
					}
					w.red = x.parent.red;
					x.parent.red = false;
					w.left.red = false;
					rightRotate( x.parent );
					x = root;
				}
			}
		}
		x.red = false;
	}

	/**
	 * Performs a left rotation on node x. It is assumed that
	 * x's right child is not <code>null</code>
	 * @param x node to rotate around
	 */
	private void leftRotate( Node x ) {
		Node y = x.right;
		x.right = y.left;
		if( y.left != nil )
			y.left.parent = x;
		y.parent = x.parent;
		if( x.parent == null )
			root = y;
		else {
			if( x == x.parent.left )
				x.parent.left = y;
			else
				x.parent.right = y;
		}
		y.left = x;
		x.parent = y;
	}

	/**
	 * Performs a right rotation on node x. It is assumed that
	 * x's left child is not <code>null</code>
	 * @param x node to rotate around
	 */
	private void rightRotate( Node x ) {
		Node y = x.left;
		// handle y's right child
		x.left = y.right;
		if( y.right != nil )
			y.right.parent = x;
		// move up y
		y.parent = x.parent;
		if( x.parent == null )
			root = y;
		else {
			if( x == x.parent.left )
				x.parent.left = y;
			else
				x.parent.right = y;
		}
		// make x right child of y
		y.right = x;
		x.parent = y;
	}

	/**
	 * Inserts given node into this tree by sorting it into the tree-structure.
	 * This method is similar to an ordinary insert-method in a binary-search-tree.
	 * @param x node to insert
	 */
	private void treeInsert( Node x ) {
		Node y = null;
		Node z = root;
		int c = 0;
		while( z != nil ) {
			y = z;
			c = comparator.compare( x.item.key, z.item.key );
			if( c < 0 )
				z = z.left;
			else
				z = z.right;
		}
		x.parent = y;
		if( y == null )
			root = x;
		else {
			if( c < 0 )
				y.left = x;
			else
				y.right = x;
		}
	}

	/**
	 * @param x root of a tree
	 * @return maximum element in x
	 */
	private Node treeMaximum( Node x ) {
		while( x.right != nil )
			x = x.right;
		return x;
	}

	/**
	 * @param x root of a tree
	 * @return minimum element in x
	 */
	private Node treeMinimum( Node x ) {
		while( x.left != nil )
			x = x.left;
		return x;
	}

	/**
	 * method determines the predecessor node of given one.
	 * @param x node
	 * @return predecessor or <code>null</code>
	 */
	private Node treePredecessor( Node x ) {
		if( x.left != nil )
			return treeMaximum( x.left );
		Node y = x.parent;
		while( y != null && x == y.left ) {
			x = y;
			y = y.parent;
		}
		return y;
	}

	/**
	 * method determines the successor node if given one.
	 * @param x node
	 * @return successor or <code>null</code>
	 */
	private Node treeSuccessor( Node x ) {
		if( x.right != nil )
			return treeMinimum( x.right );
		Node y = x.parent;
		while( y != null && x == y.right ) {
			x = y;
			y = y.parent;
		}
		return y;
	}

	public int count() {
		return count;
	}
}
